package code;

import java.util.Stack;

public class SurroundedRegions {
	
	public static class Point{
		int x,y;
		Point(int a,int b){
			x=a;
			y=b;
		}
	}
	int n,m;
	int[][] direction={{0,1},{0,-1},{1,0},{-1,0}}; 
	
	public void search(int x,int y,char[][] board){
		Stack<Point> stack=new Stack<Point>();
		Point start=new Point(x, y);
		stack.push(start);
		board[x][y]='+';
		while(!stack.isEmpty()){
			start=stack.pop();
			for(int j=0;j<4;j++){
				int s=start.x+direction[j][0];
				int t=start.y+direction[j][1];
				if(s>=0 && s<n && t>=0 && t<m && board[s][t]=='O'){
					stack.push(new Point(s,t));
					board[s][t]='+';
				}
			}
		}
	}
	
	public  void solve(char[][] board){
		
		int i,j;
		int n=board.length;
		if(n==0)	return ;
		int m=board[0].length;
		for(i=0;i<n;i++){
			if(board[i][0]=='O'){
				search(i,0,board);
			}
			if(board[i][m-1]=='O'){
				search(i,m-1,board);
			}
		}
		for(i=0;i<m;i++){
			if(board[0][i]=='O'){
				search(0,i,board);
			}
			if(board[n-1][i]=='O'){
				search(n-1,i,board);
			}
		}
		for(i=0;i<n;i++){
			for(j=0;j<m;j++){
				if(board[i][j]=='O')
					board[i][j]='X';
				else if(board[i][j]=='+')
					board[i][j]='O';
				System.out.print(board[i][j]);
			}
			System.out.println();
		}
	}
	public static void main(String[] args){
		char[][] board={{'X','X','X','X'},{'X','O','O','X'},{'X','X','O','X'},{'X','O','X','X'}};
		char[][] board1={{'O'}};
		new SurroundedRegions().solve(board1);
		
	}
}
